/*
题目: 使用机器人打印字典序最小的字符串
给你一个字符串 s 和一个机器人，机器人当前有一个空字符串 t 。执行以下操作之一，直到 s 和 t 都变成空字符串：

    删除字符串 s 的 第一个 字符，并将该字符给机器人。机器人把这个字符添加到 t 的尾部。
    删除字符串 t 的 最后一个 字符，并将该字符给机器人。机器人将该字符写到纸上。

请你返回纸上能写出的字典序最小的字符串。

https://leetcode.cn/problems/using-a-robot-to-print-the-lexicographically-smallest-string
 */
public class RobotWithString {
    public String robotWithString(String s) {
        int n = s.length();
        Stack<Character> stk = new Stack<> ();
        StringBuilder paper = new StringBuilder();

        int[] cnt = new int[26];
        for (int i = 0; i < n; i ++)
            cnt[s.charAt(i) - 'a'] ++;

        int min = 0; // 最小字母

        for (int i = 0; i < n; i ++) {
            char ch = s.charAt(i);
            // 找到最小的字母
            cnt[ch - 'a'] --;  // 放在这里可以保证, 当前字母最小的话, 马上就能弹出来
            while (min < 26 && cnt[min] == 0)   min ++;

            stk.push(ch);
            while (!stk.isEmpty() && min + 'a' >= stk.peek()) {
                paper.append(stk.pop());
            }
        }

        return paper.toString();
    }
}
